//给定一个 m x n 二维字符网格 board 和一个字符串单词 word 。如果 word 存在于网格中，返回 true ；否则，返回 false 。 
//
// 单词必须按照字母顺序，通过相邻的单元格内的字母构成，其中“相邻”单元格是那些水平相邻或垂直相邻的单元格。同一个单元格内的字母不允许被重复使用。 
//
// 
//
// 示例 1： 
// 
// 
//输入：board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], word = 
//"ABCCED"
//输出：true
// 
//
// 示例 2： 
// 
// 
//输入：board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], word = 
//"SEE"
//输出：true
// 
//
// 示例 3： 
// 
// 
//输入：board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], word = 
//"ABCB"
//输出：false
// 
//
// 
//
// 提示： 
//
// 
// m == board.length 
// n = board[i].length 
// 1 <= m, n <= 6 
// 1 <= word.length <= 15 
// board 和 word 仅由大小写英文字母组成 
// 
//
// 
//
// 进阶：你可以使用搜索剪枝的技术来优化解决方案，使其在 board 更大的情况下可以更快解决问题？ 
//
// Related Topics 数组 回溯 矩阵 👍 1739 👎 0


package com.tyrone.leetcode.editor.cn;

import java.util.LinkedList;
import java.util.Queue;

public class WordSearch {
    public static void main(String[] args) {
        Solution solution = new WordSearch().new Solution();
    }

    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        /**
         * 不允许重复使用 我觉得应该要用一个二维数组来记录本次搜索是否已经使用
         * 我想使用广度优先
         * 有哪些可以优化的点 可以先判断当前字母在不在 word之间
         * 但是我想能不能分解问题，仔细想想整个解答过程中都在执行这样一个过程
         * 1.判断当前字符是不是目前想要的，如果是则执行2
         * 2.判断上下左右有没有自己想要的下一个字母，有则执行1
         * <p>
         * 所以我们可以通过递归的方式去解决，但是如果某一次递归有问题的时候，要将状态二维数组重置。
         * <p>
         * <p>
         * 刚才看了一下网上的方法可以解决原来的数组做这个操作；
         *
         * @param board
         * @param word
         * @return
         */
//    public boolean exist(char[][] board, String word) {
//
//        int[][] arr = new int[board.length][board[0].length];
//        for (int i = 0; i < board.length; i++) {
//            for (int j = 0; j < board[i].length; j++) {
//                //找到了
//                boolean search = search(arr, board, word, 0, i, j);
//                //原本这里想的是重置掉标记数组，但是其实发现我们search()的时候会去判断到底行不行，不行的话我们就重新复制成0
//                //所以这里就没有必要
////                arr = new int[board.length][board[0].length];
//                if (search) return true;
//            }
//        }
//        return false;
//    }
//
//    private boolean search(int[][] arr,char[][] board,String word ,int index,int x ,int y){
//        if (index == word.length()) return true;
//        if (x < 0 ) return false;
//        if (x > board.length-1 ) return false;
//        if (y< 0 ) return false;
//        if (y> board[0].length-1 ) return false;
//        char ch = word.charAt(index);
//        if (board[x][y] != ch || arr[x][y] != 0) {
//            return false;
//        }
//        arr[x][y] = 1;
//        boolean flag = search(arr, board, word, index + 1, x - 1, y) ||
//                search(arr, board, word, index + 1, x + 1, y) ||
//                search(arr, board, word, index + 1, x, y - 1) ||
//                search(arr, board, word, index + 1, x, y + 1);
//        if (!flag) arr[x][y] = 0;
//        return flag;
//    }
        public boolean exist(char[][] board, String word) {
            char[] w = word.toCharArray();
            for (int i = 0; i < board.length; i++) {
                for (int j = 0; j < board[i].length; j++) {
                    boolean search = search(board, w, 0, i, j);
                    if (search) return true;
                }
            }
            return false;
        }


        private boolean search(char[][] board, char[] w, int index, int x, int y) {
            if (index == w.length) return true;
            if (x < 0) return false;
            if (x > board.length - 1) return false;
            if (y < 0) return false;
            if (y > board[0].length - 1) return false;

            if (board[x][y] != w[index]) {
                return false;
            }
            //通过异或两次的操作来恢复状态判断
            board[x][y] ^= 256;
            boolean flag = search( board, w, index + 1, x - 1, y) ||
                    search(board, w, index + 1, x + 1, y) ||
                    search(board, w, index + 1, x, y - 1) ||
                    search(board, w, index + 1, x, y + 1);
            board[x][y] ^= 256;;
            return flag;
        }
    }
//leetcode submit region end(Prohibit modification and deletion)

}